// Created by WXX on 2021/11/16 10:28
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

/**
 * 执行用时：120 ms, 在所有 C++ 提交中击败了55.43%的用户
 * 内存消耗：33.2 MB, 在所有 C++ 提交中击败了32.61%的用户
 */
class Solution {
public:
    bool isRectangleCover(vector<vector<int>> &r) {
        map<pair<int, int>, int> cnt;  // 统计每个点出现次数
        typedef long long LL;
        LL sum = 0;  // 所有小矩形的和
        for (auto x : r) {
            LL a = x[0], b = x[1], c = x[2], d = x[3];
            ++cnt[{a, b}], ++cnt[{a, d}];
            ++cnt[{c, b}], ++cnt[{c, d}];
            sum += (c - a) * (d - b);
        }

        vector<vector<int>> res;
        for (auto &[x, y] : cnt) {
            if (y == 1) res.push_back({x.first, x.second});
            else if (y == 3) return false;  // 不能出现 出现三次的点
            else if (y > 4) return false;
        }

        if (res.size() != 4) return false;  // 出现一次的点必须为4个
        sort(res.begin(), res.end());
        return sum == (LL) (res[3][0] - res[0][0]) * (res[3][1] - res[0][1]);
    }
};

int main() {

    vector<vector<int>> rectangles = {{1, 1, 3, 3},
                                      {3, 1, 4, 2},
                                      {3, 2, 4, 4},
                                      {1, 3, 2, 4},
                                      {2, 3, 3, 4}};
    cout << Solution().isRectangleCover(rectangles) << endl;  // true

    return 0;
}
